The present invention relates generally to wireless, multihop networks (sometimes also referred to as "wireless local area networks (W-LANs)" or "wireless, packet-hopping networks"), and more particularly, to a method for configuring and routing data packets within a wireless, multihop network and a wireless network for implementing the same. In particular, the present invention constitutes a significant improvement over the PaST ("PArtitioned Spanning Tree") routing algorithm and wireless network disclosed in co-pending U.S. patent application Ser. No. 08/558,447, filed Nov. 16, 1995, in the name of A. Dasgupta, which is assigned to the assignee of the present invention, the disclosure of which is herein incorporated by reference.
A network which consists of a plurality of network or individual nodes which communicate with each other and with a network control node (also referred to as a "main" or "central" node) via wireless (radio or RF) links is generally referred to as a wireless (radio or RF) network. In wireless, multihop networks, each node includes a node controller which includes a digital signal processing device (e.g., a microprocessor) and an RF transceiver. Data is communicated (transferred) between the individual nodes and the control node by a technique known as "hopping", in which individual units of data are transferred from the control node to a destination node and from an origin (source sender) node to the control node by being hopped (relayed or retransmitted rebroadcast) by one or more intermediate nodes in accordance with a network routing protocol, in all instances in which the destination or origin node does not have a direct communication link with the control node. Each of the nodes which hops or relays a packet to one or more other nodes in the network is commonly referred to as a "repeater node", or simply, "repeater". The destination node generally acknowledge receipt of a data packet from the control node by returning an acknowledgement data packet to the control node via one or more repeaters in a similar fashion.
Various logical units of data can be utilized, including packets, frames, or cells. However, for convenience of illustration of a presently preferred embodiment of the present invention, the units of data employed will be "packets" typically ranging in size from about 5-1000 bytes. In this regard, the term "packets" as used herein is intended to encompass all logical units of data, including frames or cells. Generally, packet-hopping data communications are carried out under the control of the control node, which is typically a computer on which resides the data communications control software. The packet-hopping data transfer scheme enables a reduction in the cost of the RF transceivers and compliance with FCC Part 15 requirements.
Such wireless, packet-hopping networks are particularly suitable for controlling one or more functions or systems of a building, e.g., the lighting, HVAC, and/or security systems of the building, because a wireless network offers a low-cost, indoor communication infrastructure that does not require new lines to be added to the existing structure in order to carry the network information. Further, such networks can support additional systems installed in the building, such as paging and personal communications systems (PCSs).
The control node of such building control networks is typically a building computer. The individual nodes and the building computer run different software programs which are complementary, and which together constitute the system control software. The individual nodes are typically distributed throughout the building to monitor the status/value of prescribed parameters of the building system being controlled, and to produce control signals in response to commands issued by the building computer to adjust the prescribed parameters as required. It is important that the building computer be able to send and receive data to and from each node in the network in order to properly monitor the status/value of the prescribed parameters, and to issue commands to adjust the status/value of the prescribed parameters as required, in accordance with the system control software.
An exemplary building control network is an automatic or intelligent lighting control system which monitors lighting levels, occupancy status, energy consumption as a function of time, and/or other lighting parameters of each room and/or area of the building within the network, i.e., each room and/or area of the building which is equipped with a lighting module(s) linked to a node controller (also referred as a "wall unit") which includes an RF transceiver, a digital signal processing device (e.g., microcontroller or microprocessor), and control circuitry to signal the lights to change brightness levels. Each lighting module and its associated node controller together constitute a node in the network which is under the control/management of the building computer.
In such an intelligent lighting control system, each of the lighting modules is preferably individually programmable (e.g., by building occupants), via its associated wall unit, to provide direct control of the setting of the dimming ballast thereof, and thus, direct control of the lighting level of the lamp(s) thereof. In this regard, each of the nodes includes one or more sensors (e.g., occupancy status, daylight (ambient lighting), and dimming/lighting level sensors) which provide sensor feedback data to the digital signal processing device (e.g., a microprocessor) of the node controller, which is programmed to analyze (process) the sensor feedback data and to generate control signals for adjusting the lighting level of the monitored lamp(s) associated therewith, as required, to achieve the programmed local lighting conditions.
The sensor feedback data is also transmitted by each node in the network to the building computer, when requested by the building computer to do so, or when the local lighting conditions change. The building computer analyzes (processes) the sensor feedback data in accordance with lighting system control software loaded therein, and sends control data (commands) to the individual nodes, as required, in order to adjust the lighting levels of the monitored rooms/areas of the building in accordance with the lighting system control software, e.g., to optimize the energy efficiency of the lighting system, and thereby override the programmed lighting levels provided by the individual lighting modules. Thus, in addition to being individually programmable and being capable of independent operation, the distributed modules are functionally integrated into a single building-wide network under the control of the building computer.
Data communications in such networks are generally between the building computer and the individual nodes, and vice versa, over a common communications channel (i.e., a shared channel). In order to minimize simultaneous transmissions of packets over the common network channel, a channel access protocol is utilized. The most common channel access protocol is the carrier sense multiple access (CSMA) protocol, according to which each node, prior to transmitting a packet, waits for a random delay period, and then senses the channel to determine whether it is available ("clear") or unavailable ("busy"). If the channel is sensed to be clear it transmits the packet, and if the channel is sensed to be busy, it waits for another random delay period before sensing the status of the channel again before making a further attempt to transmit the packet.
There are generally two main categories of network routing algorithms or protocols that are typically utilized in wireless, multihop networks, namely, random and deterministic routing protocols.
In accordance with random routing protocols, packets are randomly hopped through the nodes in the network from a sender node to a destination node along random routes, with no specific set of repeaters being used to effectuate the data transfer. More particularly, the sender node transmits a packet to all nodes within its transmitting range and each node which receives the packet then re-transmits or relays the packet to every node within its respective transmitting range, and so on, until the packet reaches the destination node. Typically, each packet contains a byte commonly called the "hop counter", which is decremented by each repeater until it reaches zero. Once it reaches zero, the packet is no longer repeated. The hop counter is set by the sending (transmitting) node such that the probability that the packet reaches the destination node is maximized, without dominating the network for an unduly lengthy period of time.
A significant drawback of random routing protocols is that there is a rather high probability that most, if not all, nodes in the network will handle each and every packet transmitted, thereby greatly increasing the data traffic density in the network, and thus, greatly limiting the number of different packets which can be "on the network" at any given time (i.e., the data traffic handling capacity of the network). This limits the communication efficiency of the network, as well as increasing the number of unresolvable collisions which occur. These unresolvable collisions of data packets can cause packets to be lost before they reach their destination. In this connection, in building control networks, the acknowledgement packets returned to the building computer typically converge on just a few nodes that are directly linked to the building computer, thereby resulting in a higher probability and greater number of unresolvable collisions involving such packets. Consequently, blockage of acknowledgement packets is common, thereby forcing the building computer to re-transmit a packet in order to determine whether the original packet sent was actually received by the destination node. This, of course, significantly limits the data throughput and efficiency of the network.
In accordance with conventional deterministic routing protocols, the building computer formulates routing tables on the basis of nodal connectivity information which it gathers during execution of a network initialization routine. These routing tables are then used to route packets of data from a sender node to a destination node via a specific set or "chain" of repeaters (i.e., along a predetermined route or singular path defined in the routing tables). Due to the fact that these conventional deterministic routing protocols rely upon the use of routing tables in routing data within the network, they are sometimes referred to as "tabular" routing protocols. Because each packet which is transmitted is only re-transmitted (assuming there is no direct link with the building computer) by the one or more nodes along the predetermined communication path (i.e., the specific "chain" of repeater nodes specified in the routing tables) many different packets can be transmitted (i.e., "on the network") simultaneously, thereby resulting in relatively higher network data traffic handling capacity (i.e., data throughput) than is possible using a random routing protocol.
A significant drawback of conventional tabular routing algorithms is the requirement that each node have sufficient memory to store the routing tables, and sufficient processing power to handle the logical operations which are required in order to make the routing decisions based upon the data contained in the routing tables. In this regard, many applications require inexpensive, "resource-starved" nodes, i.e., node which have minimal memory and processing power.
To this end, a non-tabular, deterministic routing algorithm which is particularly suitable for wireless, multihop networks having resource-starved nodes is disclosed in co-pending U.S. patent application Ser. No. 08/558,447, filed Nov. 16, 1995, in the name of A. Dasgupta, which is assigned to the assignee of the present invention. This routing algorithm, termed the "PaST" algorithm, enables the utilization of network nodes which employ a low-cost microcontroller and a small amount of memory (e.g., less than 10 bytes), and which can be made compact enough to be incorporated into the device, e.g. light switch or wall unit, being controlled.
More particularly, a logical Partitioned Spanning Tree (PaST) is constructed by the building computer on the basis of nodal connectivity information gathered during a network initialization procedure, and a unique logical PaST address is assigned to each of the individual network nodes in the network. The logical PaST address assigned by the building computer to each individual node uniquely defines a single set or chain of repeaters that are to be used in communicating packets back and forth between the building computer and the node, and thus, the single, predetermined communication path (route) that a packet must travel to be communicated between the building computer and the individual node. In accordance with the PaST routing protocol, each packet includes a logical address data field into which the logical PaST address of the destination node to which the packet is being transmitted, is inserted.
Since the logical PaST address inserted into the logical address data field of each packet contains all of the information necessary for routing the packet, each of the individual nodes only requires sufficient memory to store their assigned PaST address (typically less than 10 bytes), and sufficient processing power to bit-wise compare their assigned PaST address with that of the PaST address contained in the logical address data field of each packet which the node receives, in order to determine whether it should process, re-transmit, or discard the packet.
However, because of intrinsic RF constraints of wireless networks, the PaST routing protocol disclosed in co-pending U.S. patent application Ser. No. 08/558,447, filed Nov. 16, 1995, in the name of A. Dasgupta still suffers from a significant drawback. Namely, with this protocol, there is a relatively low probability of a given packet being able to reach its destination, due to its being routed along a single, predetermined communication path (i.e., a single, specific chain of repeaters).
More particularly, the reliability of node-to-node communications in indoor, wireless networks is adversely affected by phenomena such as fading and multipath (the interference of an RF signal with itself due to reflections off surfaces such as walls, floors, ceilings, furniture, etc.), whereby previously established node-to-node links can be interrupted or lost. Further, such previously established node-to-node links can be interrupted or lost by virtue of dynamic changes in the indoor environment of the building, such as certain activities of the building occupants. For example, the simple action of opening or closing or door, moving furniture, or even walking down a hallway can disrupt a node-to-node communication link. Thus, the status of any given node-to-node link within the network may vary over time from solid, to sporadic, to non-existent, depending upon a number of largely unpredictable and uncontrollable variables.
Because of these inherent link reliability problems, data packets transmitted along a singular communication path can be easily lost before they reach their destination, thus requiring such data packets to be re-transmitted, thereby degrading the communications efficiency and data throughput of the network. All that is required for a transmission to be unsuccessful is for a single link in the chain of repeaters to be broken either on the outbound ("downstream") transmission of a command data packet from the building computer to the destination node, or on the inbound ("upstream") transmission of the acknowledgement data packet from the destination node to the building computer.
If the link quality of the problematic link(s) is not resolve satisfactorily, then the packet may have to be re-routed, and/or the network reconfigured, thereby further degrading the performance of the network, and increasing its cost and complexity. In this connection, the PaST routing algorithm suffers from the shortcoming that reconfiguration of the network is difficult and time-consuming.
More particularly, although the PaST routing algorithm has a built-in capability of detecting faulty communication links, when such a faulty link is detected, the only measure which can be taken to complete a transmission which is prevented due to the faulty link (i.e., to re-route a data packet around the identified faulty link), is to reprogram the logical PaST address of each node in the logical Partitioned Spanning Tree which lies beyond the faulty node which requires a change in its connectivity in order to eliminate the faulty link. Otherwise stated, every node whose logical PaST address contains an address segment corresponding to the address of the faulty node would have to be re-programmed with a new logical PaST address. This stems from the fact that the single, predetermined communication path ("route") between the building computer and a given individual network node is completely and singularly determined by the PaST address of the given individual network node.
More particularly, since the PaST address of the given individual network node includes the most significant bits of each of its "parent" nodes in the chain of repeaters forming the single, predetermined communication path, it becomes necessary to reprogram the PaST address of each node in the logical Partitioned Spanning Tree which lies beyond the node which requires a change in its connectivity in order to eliminate the faulty link. In many instances, the required change in connectivity to eliminate the identified faulty link will require a re-initialization of the entire network. In sum, simple, dynamic reconfiguration of the network of re-routing of data packets to avoid faulty links is not possible, thereby degrading the efficacy of the PaST routing algorithm, and the data throughput of the network which utilizes this routing algorithm.
There are various known ways to address the above-described link reliability problems. One way to improve link reliability is to use higher-powered RF transceivers, and another way to improve link reliability is to use noise-limiting spread spectrum transceivers. However, both of these approaches are generally cost-prohibitive for many applications. Of course, a hard-wires network would be an ideal solution, but the cost of installing such a network in an existing structure is cost-prohibitive for most applications.
A particularly effective and novel partially random, partially deterministic routing algorithm is disclosed in co-pending U.S. patent application Ser. No. 08/608,910, filed Feb. 29, 1996, in the name of the present inventor (George A. Melnik), and assigned to the assignee of the present invention, the disclosure of which is herein incorporated by reference. This novel routing algorithm greatly increases the data throughput and communications efficiency of the network, as well as enabling a significant reduction in the hardware requirements of the networks (e.g., the required baud rate and size of the packet buffers (memory) for each network node). Nevertheless, this algorithm may not be suitable for some applications which require particularly low-cost, resource-starved nodes.
Based on the above and foregoing, it can be appreciated that there presently exists a need in the art for a method for routing data in a wireless, multihop network which overcomes the above-described drawbacks, shortcomings, and disadvantages of the presently available technology. The present invention fulfills this need in the art. In particular, the present invention encompasses a reconfigurable PaST routing algorithm (R-PaST) which incorporates simple, dynamic reconfigurability, which constitutes a significant improvement over the PaST routing algorithm disclosed in co-pending U.S. patent application Ser. No. 08/558,447, filed Nov. 16, 1995, in the name of A. Dasgupta.